Random block coordinate descent methods for linearly constrained optimization over networks

摘要

In this paper we develop random block coordinate gradient descent methods forminimizing large scale linearly constrained separable convex problems overnetworks. Since we have coupled constraints in the problem, we devise analgorithm that updates in parallel $\tau \geq 2$ (block) components periteration. Moreover, for this method the computations can be performed in adistributed fashion according to the structure of the network. However, itscomplexity per iteration is usually cheaper than of the full gradient methodwhen the number of nodes $N$ in the network is large. We prove that for thismethod we obtain in expectation an $\epsilon$-accurate solution in at most$\mathcal{O}(\frac{N}{\tau \epsilon})$ iterations and thus the convergence ratedepends linearly on the number of (block) components $\tau$ to be updated. Forstrongly convex functions the new method converges linearly. We also focus onhow to choose the probabilities to make the randomized algorithm to converge asfast as possible and we arrive at solving a sparse SDP. Finally, we describeseveral applications that fit in our framework, in particular the convexfeasibility problem. Numerically, we show that the parallel coordinate descentmethod with $\tau>2$ accelerates on its basic counterpart corresponding to$\tau=2$.